package sort;

import java.util.Arrays;

/*
* 插入排序
* */
public class InsertSort {
    public static void main(String[] args) {
        int[] arr= {8,42,3,1,14,8,3,51,66,35,2};

        insertSort(arr);
        for (int i : arr) {
            System.out.println(i);
        }
    }

    public static void insertSort(int[] arr){


        for (int i = 1; i < arr.length; i++) {

            int j = i;
            int insert = arr[i];
            while(j>0&&insert<arr[j-1]){
                //如果符合条件  带插入的数 insert备份了 可以理解为此时的待插入的位置 为虚位以待
                // 所以说若果满足条件就把前一位的数值移到后面一位 ，最后找到具体插入的位置 可以直接arr[j] = temp
                //eg  31245  第一轮:3 1245  temp=1  3 3245,13245;第二轮 13 245 ->13345 ->12345

                arr[j] = arr[j-1];
                j--;
            }
            if (j!=i){
                arr[j] = insert;
            }

        }


    }
}
